
public class HashBucket {
    public static void main(String[] args) {
        HashBucket hashBucket = new HashBucket();
        hashBucket.put(1, 100);
        hashBucket.put(2, 200);
        hashBucket.put(10, 222);
        hashBucket.put(3, 3);
        hashBucket.put(4, 44);
        hashBucket.put(5, 555);
        hashBucket.put(16, 100);
        hashBucket.put(7, 200);
        hashBucket.put(6, 222);
        hashBucket.put(18, 3);
        System.out.println(hashBucket.get(16));
        System.out.println(hashBucket.get(5));
    }

    public static class Node {
        public int key;
        public int val;
        public Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    //初始哈希表
    public Node[] elem = new Node[10];
    public int usedSize;
    //负载因子
    public static final double LOAD_FACTOR = 0.75;

    //新增元素
    public void put(int key, int val) {
        //1.通过哈希函数,找到对应链表的index
        int index = key % elem.length;
        //2.判断当前的链表是否有key
        Node cur = elem[index];
        while (cur != null) {
            //3.找到key,修改改结点的val
            if (cur.key == key) {
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        //4.如果没有key,则将新结点插入链表(这里采取头插法)
        Node newCur = new Node(key, val);
        newCur.next = elem[index];
        elem[index] = newCur;
        usedSize++;
        //5.计算当前的负载因子,如果超过则扩容
        if (getLoadFactor() >= LOAD_FACTOR) {
            upsize();
        }
    }

    //计算当前负载因子
    public double getLoadFactor() {
        return usedSize * 1.0 / elem.length;
    }

    //哈希表扩容(再次哈希)
    public void upsize() {
        //1.创建新的哈希表
        Node[] newElem = new Node[elem.length * 2];
        for (int i = 0; i < elem.length; i++) {
            Node cur = elem[i];
            while (cur != null) {
                Node curN = cur.next;
                int index = cur.key % newElem.length;
                cur.next = newElem[index];
                newElem[index] = cur;
                cur = curN;
            }
        }
        elem = newElem;
    }

    //通过key获取元素
    public int get(int key) {
        //找到key的对应下标
        int index = key % elem.length;
        Node cur = elem[index];
        //查找链表
        while (cur != null) {
            if (cur.key == key) {
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;
    }
}